package com.example.algorithm.sort;

public class QuickSort02 {
    public static void main(String[] args) {
        int[] array = {5, 3, 9, 8, 4, 2, 6, 1, 7};

        System.out.println("排序前的数组：");
        printArray(array);

        quickSort(array, 0, array.length - 1);

        System.out.println("\n排序后的数组：");
        printArray(array);
    }

    // 快速排序方法
    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {

            int pivotIndex = partition(array, low, high);

            quickSort(array, low, pivotIndex - 1);
            quickSort(array, pivotIndex + 1, high);
        }
    }

    // 划分方法
    public static int partition(int[] array, int low, int high) {
        int pivot = array[low];
        int i = low, j = high;

        while (i < j) {

            while (i < j && array[j] >= pivot) {
                j--;
            }
            if (i < j) {
                array[i++] = array[j];
            }

            while (i < j && array[i] <= pivot) {
                i++;
            }
            if (i < j) {
                array[j--] = array[i];
            }
        }

        array[i] = pivot; // 基准值的值，把它放在重合位置
        return i; // 返回方便下一轮递归
    }

    // 打印数组方法
    public static void printArray(int[] array) {
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}